package style.Leetcode.初级算法.linkedList.linkedList_20220816_2_删除链表的倒数第N个节点;

import style.Leetcode.初级算法.linkedList.ListNode;

/**
 * 给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。
 * <p>
 * 输入：head = [1,2,3,4,5], n = 2
 * 输出：[1,2,3,5]
 * 示例 2：
 * <p>
 * 输入：head = [1], n = 1
 * 输出：[]
 * 示例 3：
 * <p>
 * 输入：head = [1,2], n = 1
 * 输出：[1]
 * <p>
 * 提示：
 * 链表中结点的数目为 sz
 * 1 <= sz <= 30
 * 0 <= Node.val <= 100
 * 1 <= n <= sz
 */
public class Solution {
    /**
     * 思路：快慢指针实现
     * 1、快指针先走 n 步，慢指针再一起走
     * 2、快指针到末尾的时候，慢指针的位置就是需要删除的节点的前一个位置
     * 3、保留慢指针的next的next节点，慢指针的 next 指向 慢指针的next的next节点，实现连接
     */
    public ListNode removeNthFromEnd(ListNode head, int n) {
        if (head == null) return null;

        ListNode fastPoint = head;
        ListNode slowPoint = head;

        while (n > 0 ) {
            fastPoint = fastPoint.next;
            n--;
        }

        //如果fast为空，表示删除的是头结点
        if (fastPoint == null) return head.next;

        while (fastPoint.next != null) {
            fastPoint = fastPoint.next;
            slowPoint = slowPoint.next;
        }

        // 这里的 slowPoint 为倒数第 n+1 个节点
        slowPoint.next = slowPoint.next.next;
        return head;
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        ListNode node = new ListNode(1);
        node.next = new ListNode(2);
        node.next.next = new ListNode(3);
        node.next.next.next = new ListNode(4);
        node.next.next.next.next = new ListNode(5);

        ListNode resNode = solution.removeNthFromEnd(node, 2);

        System.out.println(resNode.toString());
    }
}
